0856. 括号的分数【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 栏

1. 📝 题目描述

• leetcode

给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：

• () 得 1 分。
• AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。
• (A) 得 2 * A 分，其中 A 是平衡括号字符串。

---

示例 1：

输入："()"
输出：1

示例 2：

输入："(())"
输出：2

示例 3：

输入："()()"
输出：2

示例 4：

输入："(()(()))"
输出：6

---

提示：

1. S 是平衡括号字符串，且只含有 ( 和 )。
2. 2 <= S.length <= 50

2. 🎯 s.1 - 栏

c

int scoreOfParentheses(char* s) {
    int stack[50], top = 0;
    stack[top++] = 0;
    for (int i = 0; s[i]; i++) {
        if (s[i] == '(') {
            stack[top++] = 0;
        } else {
            int v = stack[--top];
            stack[top - 1] += v > 0 ? 2 * v : 1;
        }
    }
    return stack[0];
}

js

/**
 * @param {string} s
 * @return {number}
 */
var scoreOfParentheses = function (s) {
  const stack = [0]
  for (const c of s) {
    if (c === '(') {
      stack.push(0)
    } else {
      const top = stack.pop()
      stack[stack.length - 1] += Math.max(2 * top, 1)
    }
  }
  return stack[0]
}

py

class Solution:
    def scoreOfParentheses(self, s: str) -> int:
        stack = [0]
        for c in s:
            if c == '(':
                stack.append(0)
            else:
                v = stack.pop()
                stack[-1] += max(2 * v, 1)
        return stack[0]

• 时间复杂度：$O(n)$，其中 n 是字符串长度
• 空间复杂度：$O(n)$

算法思路：

• 用栈维护当前层的分数，遇 ( 压入 0，遇 ) 弹出并计算
• () 计 1 分，(A) 计 2*A 分，累加到父层